Example 2 Clustering Geometric ObjectsΒΆ
In this example we will look at a few of the tools provided by the clifford package for (4,1) conformal geometric algebra (CGA) and see how we can use them in a practical setting to cluster geometric objects via the simple K-means clustering algorithm provided in clifford.tools
As before the first step in using the package for CGA is to generate and import the algebra:
[1]:
from clifford.g3c import *
print('e1*e1 ', e1*e1)
print('e2*e2 ', e2*e2)
print('e3*e3 ', e3*e3)
print('e4*e4 ', e4*e4)
print('e5*e5 ', e5*e5)
e1*e1 1.0
e2*e2 1.0
e3*e3 1.0
e4*e4 1.0
e5*e5 -1.0
The tools submodule of the clifford package contains a wide array of algorithms and tools that can be useful for manipulating objects in CGA. In this case we will be generating a large number of objects and then segmenting them into clusters.
We first need an algorithm for generating a cluster of objects in space. We will construct this cluster by generating a random object and then repeatedly disturbing this object by some small fixed amount and storing the result:
[2]:
from clifford.tools.g3c import *
import numpy as np
def generate_random_object_cluster(n_objects, object_generator, max_cluster_trans=1.0, max_cluster_rot=np.pi/8):
""" Creates a cluster of random objects """
ref_obj = object_generator()
cluster_objects = []
for i in range(n_objects):
r = random_rotation_translation_rotor(maximum_translation=max_cluster_trans, maximum_angle=max_cluster_rot)
new_obj = apply_rotor(ref_obj, r)
cluster_objects.append(new_obj)
return cluster_objects
We can use this function to create a cluster and then we can visualise this cluster with GAOnline using the built in tools in clifford.
[3]:
from clifford.tools.g3c.GAOnline import *
clustered_circles = generate_random_object_cluster(10, random_circle)
sc = GAScene()
for c in clustered_circles:
sc.add_circle(c,'rgb(255,0,0)')
print(sc)
DrawCircle((0.1279^e123) + (4.19043^e124) + (4.22973^e125) + (3.61261^e134) + (3.63692^e135) - (0.31355^e145) + (4.6038^e234) + (4.63797^e235) - (0.29491^e245) + (0.09023^e345),rgb(255,0,0));
DrawCircle((0.13624^e123) + (4.11789^e124) + (4.16301^e125) + (0.56922^e134) + (0.56879^e135) - (0.20142^e145) + (4.72909^e234) + (4.76469^e235) - (0.49005^e245) + (0.16358^e345),rgb(255,0,0));
DrawCircle((0.20298^e123) + (5.61313^e124) + (5.66647^e125) + (2.62667^e134) + (2.63857^e135) - (0.36106^e145) + (3.24011^e234) + (3.25789^e235) - (0.35967^e245) + (0.04011^e345),rgb(255,0,0));
DrawCircle((0.23944^e123) + (3.08105^e124) + (3.12167^e125) + (3.14685^e134) + (3.1633^e135) - (0.32236^e145) + (5.34735^e234) + (5.38452^e235) - (0.4289^e245) + (0.12141^e345),rgb(255,0,0));
DrawCircle((0.1013^e123) + (4.42567^e124) + (4.46911^e125) + (2.09491^e134) + (2.10957^e135) - (0.25778^e145) + (4.51329^e234) + (4.54794^e235) - (0.42162^e245) + (0.06331^e345),rgb(255,0,0));
DrawCircle((0.17837^e123) + (4.92613^e124) + (4.97518^e125) + (1.36241^e134) + (1.3624^e135) - (0.3748^e145) + (4.17222^e234) + (4.20217^e235) - (0.32013^e245) + (0.2289^e345),rgb(255,0,0));
DrawCircle((0.15596^e123) + (3.75762^e124) + (3.79807^e125) + (0.59495^e134) + (0.59041^e135) - (0.26361^e145) + (5.19848^e234) + (5.23905^e235) - (0.37078^e245) + (0.30598^e345),rgb(255,0,0));
DrawCircle((0.14383^e123) + (4.45321^e124) + (4.49965^e125) + (2.57289^e134) + (2.58686^e135) - (0.39832^e145) + (3.94378^e234) + (3.97462^e235) - (0.31866^e245) + (0.16864^e345),rgb(255,0,0));
DrawCircle((0.09195^e123) + (5.59587^e124) + (5.64712^e125) + (2.21858^e134) + (2.23352^e135) - (0.32777^e145) + (2.97129^e234) + (2.99257^e235) - (0.36112^e245) + (0.03087^e345),rgb(255,0,0));
DrawCircle((0.19282^e123) + (4.92126^e124) + (4.96927^e125) + (3.54249^e134) + (3.56519^e135) - (0.30279^e145) + (3.76694^e234) + (3.78894^e235) - (0.37646^e245) - (0.03922^e345),rgb(255,0,0));
This cluster generation function appears in clifford tools by default and it can be imported as follows:
[4]:
from clifford.tools.g3c import generate_random_object_cluster
Now that we can generate individual clusters we would like to generate many:
[5]:
def generate_n_clusters( object_generator, n_clusters, n_objects_per_cluster ):
object_clusters = []
for i in range(n_clusters):
cluster_objects = generate_random_object_cluster(n_objects_per_cluster, object_generator,
max_cluster_trans=0.5, max_cluster_rot=np.pi / 16)
object_clusters.append(cluster_objects)
all_objects = [item for sublist in object_clusters for item in sublist]
return all_objects, object_clusters
Again this function appears by default in clifford tools and we can easily visualise the result:
[6]:
from clifford.tools.g3c import generate_n_clusters
all_objects, object_clusters = generate_n_clusters(random_circle, 2, 5)
sc = GAScene()
for c in all_objects:
sc.add_circle(c,'rgb(255,0,0)')
print(sc)
DrawCircle((0.49141^e123) + (5.56981^e124) + (5.62953^e125) + (2.39079^e134) + (2.43878^e135) + (0.25335^e145) + (3.7324^e234) + (3.74798^e235) - (0.27705^e245) - (0.2887^e345),rgb(255,0,0));
DrawCircle((0.49284^e123) + (6.27603^e124) + (6.33768^e125) + (2.30357^e134) + (2.35093^e135) + (0.31493^e145) + (2.68626^e234) + (2.69461^e235) - (0.22968^e245) - (0.2191^e345),rgb(255,0,0));
DrawCircle((0.54758^e123) + (6.01734^e124) + (6.07035^e125) + (3.09223^e134) + (3.14763^e135) + (0.30934^e145) + (3.58001^e234) + (3.5953^e235) - (0.17856^e245) - (0.2758^e345),rgb(255,0,0));
DrawCircle((0.49014^e123) + (6.42641^e124) + (6.4862^e125) + (2.55851^e134) + (2.60868^e135) + (0.34575^e145) + (2.04643^e234) + (2.05093^e235) - (0.19058^e245) - (0.18598^e345),rgb(255,0,0));
DrawCircle((0.53417^e123) + (6.18018^e124) + (6.23824^e125) + (2.962^e134) + (3.01396^e135) + (0.2791^e145) + (3.07279^e234) + (3.07933^e235) - (0.25839^e245) - (0.26261^e345),rgb(255,0,0));
DrawCircle((0.19415^e123) - (1.20783^e124) - (1.23037^e125) + (1.71984^e134) + (1.78734^e135) - (0.22023^e145) + (3.14474^e234) + (3.20447^e235) - (0.0065^e245) - (0.56414^e345),rgb(255,0,0));
DrawCircle((0.16841^e123) - (1.40292^e124) - (1.43486^e125) + (1.35205^e134) + (1.41773^e135) - (0.29069^e145) + (2.71099^e234) + (2.76842^e235) + (0.03572^e245) - (0.59614^e345),rgb(255,0,0));
DrawCircle((0.19838^e123) - (1.23181^e124) - (1.25318^e125) + (1.0053^e134) + (1.0708^e135) - (0.29844^e145) + (2.85918^e234) + (2.9215^e235) - (0.07897^e245) - (0.62826^e345),rgb(255,0,0));
DrawCircle((0.18988^e123) - (1.35018^e124) - (1.38101^e125) + (1.45524^e134) + (1.52785^e135) - (0.28002^e145) + (2.61962^e234) + (2.66869^e235) + (0.07645^e245) - (0.62569^e345),rgb(255,0,0));
DrawCircle((0.25355^e123) - (1.78367^e124) - (1.81631^e125) + (1.81727^e134) + (1.88733^e135) - (0.2589^e145) + (3.24959^e234) + (3.30112^e235) + (0.05591^e245) - (0.52864^e345),rgb(255,0,0));
Given that we can now generate multiple clusters of objects we can test algorithms for segmenting them.
The function run_n_clusters below generates a lot of objects distributed into n clusters and then attempts to segment the objects to recover the clusters.
[7]:
from clifford.tools.g3c.object_clustering import n_clusters_objects
import time
def run_n_clusters( object_generator, n_clusters, n_objects_per_cluster, n_shotgunning):
all_objects, object_clusters = generate_n_clusters( object_generator, n_clusters, n_objects_per_cluster )
[new_labels, centroids, start_labels, start_centroids] = n_clusters_objects(n_clusters, all_objects,
initial_centroids=None,
n_shotgunning=n_shotgunning,
averaging_method='unweighted')
return all_objects, new_labels, centroids
Lets try it!
[8]:
from clifford.tools.g3c.object_clustering import visualise_n_clusters
object_generator = random_circle
n_clusters = 3
n_objects_per_cluster = 10
n_shotgunning = 60
all_objects, labels, centroids = run_n_clusters(object_generator, n_clusters,
n_objects_per_cluster, n_shotgunning)
sc = visualise_n_clusters(all_objects, centroids, labels, object_type='circle',
color_1=np.array([255, 0, 0]), color_2=np.array([0, 255, 0]))
print(sc)
DrawCircle((0.41416^e123) - (1.71576^e124) - (1.73546^e125) - (9.32923^e134) - (9.37817^e135) - (0.24119^e145) - (3.64757^e234) - (3.66211^e235) - (0.11334^e245) - (0.10351^e345),rgb(255, 0, 0));
DrawCircle((0.37484^e123) - (1.14249^e124) - (1.15906^e125) - (9.55155^e134) - (9.60305^e135) - (0.26537^e145) - (2.09856^e234) - (2.10676^e235) - (0.0678^e245) - (0.07935^e345),rgb(255, 0, 0));
DrawCircle((0.36539^e123) - (3.09327^e124) - (3.11945^e125) - (8.96614^e134) - (9.01401^e135) - (0.23715^e145) - (2.01499^e234) - (2.0193^e235) - (0.10787^e245) - (0.15819^e345),rgb(255, 0, 0));
DrawCircle((0.39837^e123) - (2.56654^e124) - (2.58856^e125) - (9.42048^e134) - (9.47003^e135) - (0.20155^e145) - (2.57656^e234) - (2.58392^e235) - (0.09503^e245) - (0.14646^e345),rgb(255, 0, 0));
DrawCircle((0.3984^e123) - (2.08971^e124) - (2.11247^e125) - (9.32719^e134) - (9.37637^e135) - (0.2749^e145) - (2.53441^e234) - (2.54205^e235) - (0.10475^e245) - (0.13413^e345),rgb(255, 0, 0));
DrawCircle((0.47294^e123) - (1.34194^e124) - (1.35941^e125) - (10.50574^e134) - (10.55737^e135) - (0.24167^e145) - (1.8762^e234) - (1.88112^e235) - (0.05536^e245) - (0.09553^e345),rgb(255, 0, 0));
DrawCircle((0.41094^e123) - (3.05355^e124) - (3.07905^e125) - (9.61217^e134) - (9.66053^e135) - (0.23701^e145) - (1.42093^e234) - (1.4233^e235) - (0.07059^e245) - (0.11192^e345),rgb(255, 0, 0));
DrawCircle((0.42915^e123) - (2.19818^e124) - (2.21982^e125) - (9.53501^e134) - (9.58403^e135) - (0.22978^e145) - (3.24171^e234) - (3.25286^e235) - (0.10635^e245) - (0.12244^e345),rgb(255, 0, 0));
DrawCircle((0.37642^e123) - (1.90631^e124) - (1.92603^e125) - (9.37866^e134) - (9.42892^e135) - (0.23666^e145) - (2.50819^e234) - (2.51715^e235) - (0.08601^e245) - (0.11177^e345),rgb(255, 0, 0));
DrawCircle((0.43222^e123) - (3.10797^e124) - (3.13276^e125) - (9.58428^e134) - (9.63228^e135) - (0.2046^e145) - (2.71428^e234) - (2.72298^e235) - (0.09315^e245) - (0.10859^e345),rgb(255, 0, 0));
DrawCircle(-(0.33916^e123) - (4.11373^e124) - (4.17486^e125) - (2.89344^e134) - (2.90286^e135) + (0.40717^e145) - (3.62831^e234) - (3.66959^e235) + (0.15331^e245) - (0.2513^e345),rgb(0, 255, 0));
DrawCircle(-(0.29463^e123) - (3.95114^e124) - (4.01055^e125) - (1.72918^e134) - (1.72763^e135) + (0.36944^e145) - (3.99939^e234) - (4.04409^e235) + (0.207^e245) - (0.28336^e345),rgb(0, 255, 0));
DrawCircle(-(0.28684^e123) - (4.40369^e124) - (4.46543^e125) - (1.94611^e134) - (1.94668^e135) + (0.41012^e145) - (3.36948^e234) - (3.41093^e235) + (0.08897^e245) - (0.27449^e345),rgb(0, 255, 0));
DrawCircle(-(0.34157^e123) - (4.95744^e124) - (5.01735^e125) - (0.97251^e134) - (0.95987^e135) + (0.35406^e145) - (3.99184^e234) - (4.03404^e235) + (0.08776^e245) - (0.26788^e345),rgb(0, 255, 0));
DrawCircle(-(0.33821^e123) - (4.03593^e124) - (4.09416^e125) - (1.41435^e134) - (1.40434^e135) + (0.36301^e145) - (4.33611^e234) - (4.38125^e235) + (0.2079^e245) - (0.31715^e345),rgb(0, 255, 0));
DrawCircle(-(0.2502^e123) - (4.12789^e124) - (4.19149^e125) - (1.92773^e134) - (1.93012^e135) + (0.45066^e145) - (3.00635^e234) - (3.04482^e235) + (0.12955^e245) - (0.26772^e345),rgb(0, 255, 0));
DrawCircle(-(0.33771^e123) - (4.12116^e124) - (4.18038^e125) - (2.29212^e134) - (2.29456^e135) + (0.37212^e145) - (4.08317^e234) - (4.12809^e235) + (0.16781^e245) - (0.27536^e345),rgb(0, 255, 0));
DrawCircle(-(0.28803^e123) - (4.65593^e124) - (4.72089^e125) - (1.33454^e134) - (1.32867^e135) + (0.39577^e145) - (3.38591^e234) - (3.42162^e235) + (0.18642^e245) - (0.23438^e345),rgb(0, 255, 0));
DrawCircle(-(0.25554^e123) - (4.24357^e124) - (4.30341^e125) - (1.6075^e134) - (1.6078^e135) + (0.37151^e145) - (3.65746^e234) - (3.70162^e235) + (0.12304^e245) - (0.27359^e345),rgb(0, 255, 0));
DrawCircle(-(0.27547^e123) - (4.80205^e124) - (4.86694^e125) - (1.30239^e134) - (1.3002^e135) + (0.34497^e145) - (3.51969^e234) - (3.55594^e235) + (0.19722^e245) - (0.19936^e345),rgb(0, 255, 0));
DrawCircle(-(0.52902^e123) - (0.30001^e124) - (0.40227^e125) + (3.58171^e134) + (3.54422^e135) - (0.71368^e145) + (3.70477^e234) + (3.73759^e235) - (0.69759^e245) - (0.4848^e345),rgb(127, 127, 0));
DrawCircle(-(0.48735^e123) + (1.43366^e124) + (1.3316^e125) + (4.24331^e134) + (4.20501^e135) - (0.77594^e145) + (3.52733^e234) + (3.55988^e235) - (0.83442^e245) - (0.5606^e345),rgb(127, 127, 0));
DrawCircle(-(0.44135^e123) + (0.10025^e124) - (0.00362^e125) + (3.27356^e134) + (3.2396^e135) - (0.76274^e145) + (2.84462^e234) + (2.87623^e235) - (0.67668^e245) - (0.45332^e345),rgb(127, 127, 0));
DrawCircle(-(0.36826^e123) + (1.25339^e124) + (1.14821^e125) + (2.79625^e134) + (2.75946^e135) - (0.67341^e145) + (2.85182^e234) + (2.87477^e235) - (0.89262^e245) - (0.45919^e345),rgb(127, 127, 0));
DrawCircle(-(0.57689^e123) + (0.73373^e124) + (0.63215^e125) + (5.00554^e134) + (4.96892^e135) - (0.83486^e145) + (3.92867^e234) + (3.96447^e235) - (0.73734^e245) - (0.55999^e345),rgb(127, 127, 0));
DrawCircle(-(0.46021^e123) - (0.43897^e124) - (0.54261^e125) + (2.35618^e134) + (2.31845^e135) - (0.56657^e145) + (3.50999^e234) + (3.53789^e235) - (0.7638^e245) - (0.43059^e345),rgb(127, 127, 0));
DrawCircle(-(0.54777^e123) - (0.4305^e124) - (0.53421^e125) + (3.87364^e134) + (3.8319^e135) - (0.76622^e145) + (4.02746^e234) + (4.04853^e235) - (0.74598^e245) - (0.45588^e345),rgb(127, 127, 0));
DrawCircle(-(0.44931^e123) + (0.64036^e124) + (0.53776^e125) + (4.02518^e134) + (3.98826^e135) - (0.86652^e145) + (2.67667^e234) + (2.70912^e235) - (0.65745^e245) - (0.5106^e345),rgb(127, 127, 0));
DrawCircle(-(0.4949^e123) + (1.84178^e124) + (1.73967^e125) + (4.87359^e134) + (4.83511^e135) - (0.86234^e145) + (3.41733^e234) + (3.44951^e235) - (0.82481^e245) - (0.58252^e345),rgb(127, 127, 0));
DrawCircle(-(0.37902^e123) + (0.06023^e124) - (0.04203^e125) + (2.59196^e134) + (2.55417^e135) - (0.6933^e145) + (2.52132^e234) + (2.55384^e235) - (0.68542^e245) - (0.47377^e345),rgb(127, 127, 0));
DrawCircle(-(0.30169^e123) - (4.36459^e124) - (4.4262^e125) - (1.76142^e134) - (1.75957^e135) + (0.38649^e145) - (3.715^e234) - (3.75668^e235) + (0.15562^e245) - (0.26617^e345),rgb(0,0,0));
DrawCircle(-(0.47678^e123) + (0.50064^e124) + (0.39711^e125) + (3.66446^e134) + (3.62675^e135) - (0.75608^e145) + (3.33769^e234) + (3.36806^e235) - (0.75661^e245) - (0.49738^e345),rgb(0,0,0));
DrawCircle((0.40895^e123) - (2.22815^e124) - (2.24992^e125) - (9.56303^e134) - (9.61267^e135) - (0.23846^e145) - (2.48278^e234) - (2.49061^e235) - (0.08947^e245) - (0.1183^e345),rgb(0,0,0));